package leetcode.lcp0023;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public boolean isMagic(int[] target) {
		int n = target.length;
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = i + 1;
		}
		int[] shuffle = shuffle(arr, 0);
		int k = 0, t = 0;
		while (t < n && shuffle[k] == target[t]) {
			k++;
			t++;
		}
		if (k == n) {
			return true;
		}
		if (k == 0)
			return false;
		int p = k;
		while (shuffle.length > 0) {
			shuffle = shuffle(shuffle, p);
			p = 0;
			while (p < Math.min(k, shuffle.length)) {
				if (shuffle[p] != target[t]) {
					return false;
				}
				p++;
				t++;
			}
		}
		return true;
	}

	private int[] shuffle(int[] arr, int start) {
		int len = arr.length - start;
		int[] ans = new int[len];
		for (int i = start, f = 0, e = 0, o = len >> 1; i < arr.length; i++, f ^= 1) {
			int num = arr[i];
			if ((f & 1) == 0) {
				ans[o++] = num;
			} else {
				ans[e++] = num;
			}
		}
		return ans;
	}

	@Override
	public void debug4() {

		H.compare(true, this.isMagic(H.str2array3(
				"[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33]")));
		H.compare(false, this.isMagic(H.str2array3("[5,4,3,2,1]")));
		H.compare(true, this.isMagic(H.str2array3("[2,4,3,1,5]")));
		H.compare(true, this.isMagic(H.str2array3(
				"[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,55,59,63,67,53,57,61,65,69]")));
		H.compare(false, this.isMagic(H.str2array3(
				"[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,35,41,33,39,37,47,43,45]")));
		H.compare(true, this.isMagic(H.str2array3("[2,4,6,10,3,7,1,9,8,5]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
